//https://leetcode.cn/problems/sliding-window-maximum/
package codeRandomThoughts.Test239滑动窗口最大值;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

class MyQueue3 {
    Deque<Integer> queue;

    public MyQueue3() {
        queue = new LinkedList<>();
    }

    public int getFront() {
        return queue.getFirst();
    }

    //把比自己小的元素都弹出去 自己再进去
    public void push(int value) {
        while (!queue.isEmpty() && queue.getLast() < value) {
            queue.pollLast();
        }

        queue.offerLast(value);
    }

    //弹出指定的元素
    public void pop(int value) {
        if (value == queue.getFirst()) {
            queue.removeFirst();
        }
    }
}

public class Solution3 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length - k + 1];
        MyQueue3 queue = new MyQueue3();
        //滑动窗口左右边界
        int left = 0;
        int right = 0;

        //初始化滑动窗口
        while (right <= k - 1) {
            queue.push(nums[right]);
            right++;
        }
        right--;//上面多减了一次,补回来
        res[0] = queue.getFront();

        //窗口开始滑动
        while (right < nums.length - 1) {
            //left右移
            queue.pop(nums[left]);
            left++;
            //right右移
            right++;
            queue.push(nums[right]);

            //记录当前滑动窗口的最大值
            res[left] = queue.getFront();
        }

        return res;
    }
}